#include "sort.h"
/**************************************************
                平均     最坏     最好       空间
冒泡<交换<比较   n^2      n^2       n          1          稳定
快排<交换<比较   nlogn    n^2     nlogn       logn        不稳定
插入<插入<比较   n^2      n^2       n          1          稳定
希尔<插入<比较   n^1.3    n^2      n           1          稳定
选择<选择<比较   n^2      n^2       n          1          稳定
堆  <选择<比较   nlogn   nlogn    nlogn        1          不稳定
归并<归并<比较   nlogn   nlogn    nlogn        n          不稳定

计数   <非比较    n+k       n+k     n+k       n+k        稳定
桶     <非比较    n+k       n^2      n        n+k        稳定
基数   <非比较    n*k       n*k     n*k       n+k        稳定

冒泡和插入在时空和稳定上性能完全相同，选择是最差劲的一种，即使是最好也是 n^2 的复杂，其他和冒泡、插入一致


非交换排序都是牺牲空间，换取时间搞笑（计数、桶【计数升级】、基数），
基数：原理与桶完全不同，类似于人类的住址搜索思维，升序【西方，先看低位（小的地址名），最后高位】，降序【中国，先看高位（大的地址区域），最后个位】
交换中快排【冒泡升级】、希尔【插入升级】、堆、归并是做到时间上的提升，其中冒泡和归并需要增加空间复杂度
大部分时候n^1.3是小于nlogn的，可以带入4,8,16等数一试，因此希尔在时间空间稳定性上都是优势。

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，
而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，
当然d要远远小于n，因此基本上还是线性级别的。
基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。

关于时间复杂度：
平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；

O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序

线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

关于稳定性：
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
****************************************************/
void testSort()
{
    int data[]={2,45,6,8,22,  11,37,66,3,54,  55,7,68,17,18,  19,98,86,85,4,  10,32,29,4,51};
    int num=25;
    sort_base * p_sort;
    std::cout << "Hello World!--sort_Bubble--" << std::endl;
    p_sort = new sort_Bubble(data,num);
    delete p_sort;
}
